package 所有的题类.ZF.分治算法;

public class 数组中的第K个最大元素 {

    public static void main(String[] args) {
        int[]array=new int[]{5,2,7,9,3,12,35,1};

        System.out.println(digui(array, 0, array.length - 1, 5));
    }

    public static int digui(int[]nums,int start,int end,int k){
        //选取一个中间值，将中间放到数组的中间位置
        //5,2,7,9,3,12,35,1
        int i=start;
        int j=end;
        int midNum=nums[i];
        while (i<j){
            //找到第一次大于mid的那个值
            while (midNum<=nums[j] && i<j){
                j--;
            }
            if(i<j){
                nums[i]=nums[j];
                i++;
            }

            while (nums[i]<=midNum && i<j){
               i++;
           }
            if(i<j){
                nums[j]=nums[i];
                j--;
            }
        }
        nums[i]=midNum;
        int mid=i-start;
        if(mid==(k-1)){
            return nums[i];
        }else if((k-1)<mid){//left在k的左边
            return digui(nums,start,i-1,k);
        }else{
            return digui(nums,(i+1),end,(k-(i-start)-1));
        }
    }
}
